import java.util.ArrayList;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 08 - 29
 * Time: 22:11
 */
//牛客 在二叉树中找到两个节点的最近公共祖先
public class Solution3 {
    //法一 官方推荐方法(用顺序表存储路径）
    //记录是否找到到o的路径
    public boolean flag = false;
    //求得根节点到目标节点的路径
    public void dfs(TreeNode root, ArrayList<Integer> path, int o){
        if(root == null)
            return;
        path.add(root.val);//将当前节点加入顺序表
        if(root.val == o){//判断当前节点是否为目标节点
            flag = true;
            return;
        }
        //判断当前节点的左子树和右子树中是否存在目标节点
        dfs(root.left, path, o);
        dfs(root.right, path, o);
        //找到
        if(flag)
            return;
        //当前节点不是目标节点，当前节点的左子树和右子树中不存在目标节点，则在顺序表中去掉当前节点
        path.remove(path.size() - 1);
    }
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        ArrayList<Integer> path1 = new ArrayList<Integer>();
        ArrayList<Integer> path2 = new ArrayList<Integer>();
        //求根节点到两个节点的路径
        dfs(root, path1, o1);
        //重置flag，查找下一个
        flag = false;
        dfs(root, path2, o2);
        int res = 0;
        //比较两个路径，找到第一个不同的点
        for(int i = 0; i < path1.size() && i < path2.size(); i++){
            int x = path1.get(i);
            int y = path2.get(i);
            if(x == y)
                //最后一个相同的节点就是最近公共祖先
                res = x;
            else
                break;
        }
        return res;
    }




    //法二 官方推荐方法(用栈存储路径）
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        Stack<TreeNode> stackp = new Stack<>();
        Stack<TreeNode> stackq = new Stack<>();
        getPath(root, p, stackp);
        getPath(root, q, stackq);
        int sizep = stackp.size();
        int sizeq = stackq.size();
        if(sizep > sizeq) {
            int size = sizep - sizeq;
            while(size != 0) {
                stackp.pop();
                size--;
            }
        }else {
            int size = sizeq - sizep;
            while(size != 0) {
                stackq.pop();
                size--;
            }
        }
        while(!stackq.isEmpty()) {
            if(stackp.peek().equals(stackq.peek())) {
                return stackp.peek();
            }
            stackp.pop();
            stackq.pop();
        }
        return null;
    }
    boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if(root == null) {
            return false;
        }
        stack.push(root);
        if(root == node) {
            return true;
        }

        boolean flg1 = getPath(root.left, node, stack);
        if(flg1) {
            return true;
        }
        boolean flg2 = getPath(root.right, node, stack);
        if(flg2) {
            return true;
        }
        stack.pop();
        return false;
    }




    //法三 官方方法
    public int lowestCommonAncestor1 (TreeNode root, int o1, int o2) {
        if(root == null) return -1;
        if(root.val == o1 || root.val == o2) {
            return root.val;
        }
        int leftCommonAncestor = lowestCommonAncestor1 (root.left, o1, o2);
        int rightCommonAncestor = lowestCommonAncestor1 (root.right, o1, o2);
        if(leftCommonAncestor != -1 && rightCommonAncestor != -1) {
            return root.val;
        }
        if(leftCommonAncestor != -1) {
            return leftCommonAncestor;
        }
        return rightCommonAncestor;
    }
}
